// ConvertSortedList2BST.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};



struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == head) return NULL;
        if(NULL == head->next) {
            TreeNode* root = new TreeNode(head->val);
            return root;
        }
        ListNode* pTail = head;
        while(pTail->next)
            pTail = pTail->next;
        return Help(head, head, pTail);
    }
    
    TreeNode* Help(ListNode* head, ListNode* start, ListNode* end)
    {
        if(NULL == start || NULL == end || end->val < start->val)
            return NULL;
        if(start == end){
            TreeNode* root = new TreeNode(start->val);
            return root;
        }
        
        ListNode* pB = start; ListNode* pA = start; ListNode* pLeftEnd = NULL;
        
        while(pA!= end)
        {
            pLeftEnd = pB;
            pB= pB->next;
            pA = pA->next->next;
            
        }
        
        TreeNode* root = new TreeNode(pB->val);
        TreeNode* L = Help(head, start, pLeftEnd);
        TreeNode* R = Help(head, pB->next, end);
        
        root->left = L;
        root->right = R;
        
        return root;
    }
};
int _tmain(int argc, _TCHAR* argv[])
{
	ListNode* head = new ListNode(1);
	ListNode* p = head;
	for(int i=2; i<=7; i++)
	{
		p->next = new ListNode(i);
		p = p->next;
	}

	Solution S;
	S.sortedListToBST(head);
	return 0;
}

